Задача разрешимости

Задача разрешимости (проблема разрешимости) — вопрос, сформулированный в рамках какой-либо формальной системы, требующий ответа «да» или «нет», возможно, зависящего от значений некоторых входных параметров.

Например, проблема «даны два числа: $x$ и $y$; делится ли $x$ на $y$ без остатка?» является проблемой разрешимости. Ответ может быть дан либо «да», либо «нет» и зависит от значений $x$ и $y$. Метод решения проблемы разрешимости, представленный в форме алгоритма, называется разрешающей процедурой для этой проблемы. Так, разрешающая процедура для проблемы из примера выше должна определять совокупность действий, которые следует предпринять для проверки делимости нацело $x$ на $y$ для данных чисел. Один из таких алгоритмов — деление столбиком — изучается в начальной школе. Остаток, равный нулю, означает ответ «да», в противном случае — «нет». Проблема разрешимости, для которой существует разрешающая процедура, называется разрешимой.

Не все математические задачи могут быть сформулированы как проблемы разрешимости. Вычисление произведения двух чисел, поиск наиболее быстрого алгоритма умножения чисел и оптимизационные задачи, в частности задача коммивояжёра в классической постановке, не являются проблемами разрешимости, поскольку их невозможно сформулировать так, чтобы ответом к задаче было бы «да» или «нет».

Исследования в области теории рекурсии часто сфокусированы на проблемах разрешимости, поскольку к ним без потери общности сводятся многие задачи.

См. также

• Проблема разрешения
• Алгоритмическая разрешимость

Литература

• Мальцев А. И., Алгоритмы и рекурсивные функции, Наука, 1986.
• Daniel Kroening & Ofer Strichman, Decision procedures, Springer, ISBN 978-3-540-74104-6
• Hartley Rogers, Jr., The Theory of Recursive Functions and Effective Computability, MIT Press, ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1